package com.sicheng.lc.周赛.分类.图论.迷宫or优先队列;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/2 20:15
 */
public class 迷宫达到角落 {
    // 到达角落需要移除障碍物的最小数目，此题和蓝桥杯目录的迷宫系列一样
    //https://leetcode.cn/problems/minimum-obstacle-removal-to-reach-corner/

    public int minimumObstacles(int[][] grid) {
        return bfs(grid);
    }

    int[][] d = {
            {0, 1}, {0, -1}, {1, 0}, {-1, 0}
    };

    private int bfs(int[][] grid) {

        int m = grid.length;
        int n = grid[0].length;

        PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[2]));
        heap.add(new int[]{0, 0, grid[0][0]});
        grid[0][0] = -1;

        while (!heap.isEmpty()) {
            int[] ints = heap.poll();
            int x0 = ints[0], y0 = ints[1], w0 = ints[2];

            for (int[] value : d) {
                int x = x0 + value[0];
                int y = y0 + value[1];
                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] != -1) {
                    int w = w0 + grid[x][y];
                    if (x == m - 1 && y == n - 1) {
                        return w;
                    }
                    heap.add(new int[]{x, y, w});
                    grid[x][y] = -1;
                }
            }
        }

        return -1;

    }
}
